#include "common.h"

class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> ret;
        int sz_p = p.size();
        int sz_s = s.size();
        // s.substr(0, sz);
        int begin = 0;
        while (begin < sz_s)
        {
            if (checkAnagram(s.substr(begin, sz_p), p))
            {
                ret.push_back(begin);
                ++begin;
                while (begin < sz_s)
                {
                    if (s[begin - 1] == s[begin + sz_p - 1])
                    {
                        ret.push_back(begin);
                        ++begin;
                    }
                    else
                        break;
                }
            }
            // 时间复杂度需要低

            ++begin;
        }
        return ret;
    }
    bool checkAnagram(string s1, string s2)
    {
        unordered_map<char, int> map1;
        unordered_map<char, int> map2;
        for (char c : s1)
            ++map1[c];
        for (char c : s2)
            ++map2[c];

        for (char i = 'a'; i <= 'z'; ++i)
        {
            if (map1[i] != map2[i])
                return false;
        }
        return true;
    }
};
class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        int hash1[30], hash2[30];
        vector<int> ret;
        memset(hash1, 0, sizeof(hash1));
        memset(hash2, 0, sizeof(hash2));
        for(auto ch : p)
        {
            hash1[ch - 'a']++;
        }

        int lp = p.size();
        int ls = s.size();
        for(int left = 0,right = 0, cnt = 0; right < ls; right++)
        {
            char in = s[right] - 'a';
            if(++hash2[in] <= hash1[in]) cnt++;
            
            if(right - left + 1 > lp)
            {
                char out = s[left++] - 'a';
                if(hash2[out]-- <= hash1[out]) cnt--;

            } 
            if(cnt == lp) ret.push_back(left);
        }
        return ret;
    }
};